In some situations, multiple computational tasks to be executed are defined and are then assigned to one or more computational locations to be actually executed. For example, from a user's perspective a laptop computer may be running a word processor, playing background music, and receiving an email. Each of these activities involves one or more computational tasks. The word processor, for example, may involve a keyboard-reading task, a spell-checking task, and a screen update task. Within the laptop, a task scheduler or other facility is responsible for assigning the various tasks to the processor(s) to be executed. Depending on one's point of view, one may speak of assigning the tasks to the processor(s), or speak of assigning the processor(s) to the tasks. Either way, a mapping is made between one or more tasks and one or more processors.
In computing systems that are larger than a single laptop or other single device, hundreds or thousands of tasks may await assignment at any given point. After being assigned to particular servers or virtual machines, for example, the assigned tasks will be executed at the assigned location. Algorithms for assigning tasks in a system of computing devices are sometimes referred to as “task distribution” or “task allocation” algorithms. Again, one may speak either of assigning a task to a server, or of assigning a server to a task, for example.
Tasks may be randomly assigned to their execution locations. Tasks may be assigned locations depending on task priority, e.g., by giving kernel tasks and interrupts higher priority than some other tasks. When multiple servers (for example) are available, tasks may be assigned in a round-robin manner, e.g., in a two-server system task 1 is assigned server 1, task 2 is assigned server 2, task 3 is assigned server 1, task 4 is assigned server 2, and so on. Tasks may be assigned in a manner that balances the expected (or actual) workloads imposed on the servers, to avoid server idle time or at least give each server roughly the same amount of idle time. Combinations of these approaches may also be used, e.g., by initially assigning tasks to virtual machines randomly and then load balancing based on sampled or reported workloads as the tasks execute.